﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>


//左闭右开
int low_abound(int* a, int right, int target)
{
    int left = 0;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (a[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return left;
}

int cmp_int(int* e1, int* e2)
{
    return ((*e1) - (*e2));
}
long long countFairPairs(int* nums, int numsSize, int lower, int upper) {
    qsort(nums, numsSize, sizeof(int), cmp_int);

    long long ans = 0;
    int i = 0;
    for (i = 0; i < numsSize - 1; i++)
    {
        int idxupper = low_abound(nums, numsSize-1, upper - nums[i + 1]+1);
        int idxlow = low_abound(nums, numsSize-1, lower - nums[i + 1]+1) - 1;
        ans += (idxupper - idxlow);
    }
    return ans;
}

int main()
{
    int nums[] = { 0,1,7,4,4,5 };
    int sz = sizeof(nums) / sizeof(nums[0]);
    int lower = 3;
    int upper = 6;
    long long ret = countFairPairs(nums,sz,lower,upper);
    printf("%lld\n", ret);
    return 0;
}